package middle;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution_22 {

    public List<String> generateParenthesis(int n) {
        char[] chars = new char[n << 1];
        List<String> list = new ArrayList<>();
        dps(list, chars, 0, 0, 0);
        return list;
    }

    /**
     *
     * @param list 返回结果集
     * @param chars 当前记录值
     * @param leftNum 左括号的相对数量
     * @param leftTotalNum 左括号的绝对数量
     * @param charsIndex 当前chars数组待填入的下标
     */
    private void dps(List<String> list, char[] chars, int leftNum, int leftTotalNum, int charsIndex) {
        int leftNumLimit = chars.length >> 1;
        if (charsIndex == chars.length) {
            list.add(new String(chars));
            return;
        }
        if (leftTotalNum < leftNumLimit) {
            // 如果左括号的绝对数量没有到上限，就可以选择左括号
            chars[charsIndex] = '(';
            dps(list, chars, leftNum + 1, leftTotalNum + 1, charsIndex + 1);
        }
        if (leftNum >0) {
            // 如果左括号的相对数量大于0，就可以选择右括号
            chars[charsIndex] = ')';
            dps(list, chars, leftNum - 1, leftTotalNum, charsIndex + 1);
        }
    }

    public static void main(String[] args) {
        Solution_22 model = new Solution_22();
        System.out.println(model.generateParenthesis(3));
        System.out.println(model.generateParenthesis(1));
    }
}
